contents

위상 정렬(Topological sort) 은 방향 비순환 그래프(DAG) 에 있는 정점들의 선형 순서를 생성하는 알고리즘입니다. 이 순서에서는, 정점 u에서 v로 가는 모든 방향 간선에 대해 u가 v보다 항상 먼저 나옵니다.

의존성이 있는 작업들의 집합으로부터 유효한 "할 일 목록"을 만드는 방법이라고 생각하면 쉽습니다. 만약 작업 B보다 작업 A를 먼저 해야 한다면, 위상 정렬은 A가 B보다 항상 먼저 나타나는 순서를 보장해 줍니다.

비유: 아침에 옷을 입는 것과 같습니다. 신발을 신기 전에 양말을 신어야 하고, 재킷을 입기 전에 셔츠를 입어야 합니다. 위상 정렬은 [양말, 셔츠, 신발, 재킷]과 같은 유효한 순서를 제공합니다. [신발, 양말, ...]은 유효하지 않은 순서입니다.

전제 조건: 방향 비순환 그래프 (DAG)

위상 정렬은 오직 DAG에서만 가능합니다. 이것이 무엇을 의미하는지 살펴보겠습니다.

• 방향성(Directed): 간선은 의존성을 나타내는 한 방향을 가집니다. A → B는 A가 B의 선행 조건임을 의미합니다.
• 비순환(Acyclic): 그래프에 사이클이 없습니다. 사이클은 "신발을 신으려면 먼저 양말을 신어야 하는데, 양말을 신으려면 먼저 신발을 신어야 한다"와 같은 불가능한 상황을 나타냅니다. 사이클이 있는 그래프에서는 위상 정렬을 만들 수 없습니다.

작동 원리: 두 가지 주요 알고리즘

위상 정렬을 수행하는 두 가지 일반적인 알고리즘이 있습니다.

1. 칸의 알고리즘 (너비 우선 탐색 기반)

이 알고리즘은 직관적이며, 더 이상 의존성이 없는 정점들을 점진적으로 제거하는 방식으로 작동합니다.

핵심 아이디어: 어떤 시점에서든 남아있는 선행 조건이 없는 작업이 적어도 하나는 반드시 존재합니다. 이 작업을 수행하면, 다른 작업들의 선행 조건이 해결될 수 있습니다. 모든 작업이 끝날 때까지 이를 반복합니다.

주요 데이터: 각 정점의 진입 차수(in-degree), 즉 들어오는 간선의 수를 사용합니다.

단계:

1. 진입 차수 계산: 그래프의 모든 정점에 대한 진입 차수를 계산합니다.
2. 큐 초기화: 큐를 만들고 진입 차수가 0인 모든 정점을 추가합니다. 이들이 선행 조건이 없는 시작점입니다.
3. 큐 처리:
   • 큐가 비어있지 않은 동안, 정점 u를 큐에서 꺼냅니다(dequeue).
   • u를 위상 정렬된 리스트에 추가합니다.
   • u가 가리키는 각 이웃 v에 대해:
     • v의 진입 차수를 1 감소시킵니다 (선행 조건인 u가 "완료"되었으므로).
     • 만약 v의 진입 차수가 0이 되면, v를 큐에 추가합니다.
4. 종료: 큐가 비면 알고리즘이 끝납니다. 만약 정렬된 리스트의 정점 수가 그래프의 전체 정점 수보다 적다면, 이는 그래프에 사이클이 있다는 의미입니다.

2. 깊이 우선 탐색 (DFS) 기반 알고리즘

이 알고리즘은 재귀적인 접근 방식을 사용합니다. 핵심 통찰은 한 정점은 그 모든 자손들이 방문되고 완료된 후에야 "완료"된 것으로 간주될 수 있다는 점입니다.

핵심 아이디어: 위상 정렬은 DFS 순회에서 정점들의 "완료 시간"의 역순입니다.

단계:

1. 초기화: 정렬된 결과를 저장할 빈 리스트와 방문한 정점을 추적할 집합을 만듭니다.
2. 반복 및 방문: 그래프의 모든 정점을 순회합니다. 만약 정점이 방문되지 않았다면, 그 정점에서 시작하는 DFS를 수행합니다.
3. DFS 함수 (dfs(u)):
   • 현재 정점 u를 방문했다고 표시합니다.
   • u의 각 이웃 v에 대해:
     • v가 방문되지 않았다면, 재귀적으로 dfs(v)를 호출합니다.
   • u의 모든 자손들을 방문한 후에, u를 결과 리스트의 맨 앞에 추가합니다.
4. 종료: 최종 리스트가 위상 정렬된 순서입니다.

상세 예제

다음과 같은 과목 선수 조건 그래프를 사용해 보겠습니다.

CS101 → CS201 CS101 → CS102 CS201 → CS301 CS102 → CS301

칸의 알고리즘(BFS) 사용:

1. 진입 차수:
   • CS101: 0
   • CS102: 1
   • CS201: 1
   • CS301: 2
2. 큐 초기화: 진입 차수가 0인 CS101을 큐에 추가합니다. 큐: [CS101]
3. 처리:
   • CS101을 디큐합니다. 정렬된 리스트: [CS101].
   • 이웃인 CS201과 CS102를 봅니다.
   • CS201의 진입 차수를 0으로 감소시키고 큐에 추가합니다.
   • CS102의 진입 차수를 0으로 감소시키고 큐에 추가합니다.
   • 큐: [CS201, CS102]
4. 처리:
   • CS201을 디큐합니다. 정렬된 리스트: [CS101, CS201].
   • 이웃인 CS301을 보고 진입 차수를 1로 감소시킵니다 (아직 0이 아님).
   • 큐: [CS102]
5. 처리:
   • CS102를 디큐합니다. 정렬된 리스트: [CS101, CS201, CS102].
   • 이웃인 CS301을 보고 진입 차수를 0으로 감소시키고 큐에 추가합니다.
   • 큐: [CS301]
6. 처리:
   • CS301을 디큐합니다. 정렬된 리스트: [CS101, CS201, CS102, CS301].
   • 이웃이 없습니다.
   • 큐: []

큐가 비었습니다. 유효한 위상 정렬은 [CS101, CS201, CS102, CS301] 입니다. 결과가 항상 유일하지는 않다는 점에 유의하세요. [CS101, CS102, CS201, CS301]도 유효한 정렬입니다.

실제 적용 사례 🌍

• 작업 스케줄링: Maven이나 Gradle과 같은 빌드 시스템에서, 의존성이 있는 작업들이 필요한 프로젝트보다 먼저 빌드되도록 작업을 위상 정렬합니다.
• 과목 선수 조건: 대학교 학위 취득을 위한 유효한 수강 순서를 결정합니다.
• 스프레드시트 셀 계산: 다른 셀에 의존하는 셀의 값을 계산합니다.
• 소프트웨어 의존성 해결: npm이나 pip와 같은 패키지 관리자는 패키지를 올바른 순서로 설치하기 위해 위상 정렬을 사용합니다.

시간 복잡도

칸의 알고리즘과 DFS 기반 알고리즘 모두 모든 정점과 간선을 정확히 한 번씩 방문하기 때문에 시간 복잡도는 O(V + E) 입니다. 여기서 V는 정점의 수이고 E는 간선의 수입니다.

references